上一篇，我們透過找零錢問題看到，Greedy 每一步都選擇眼前看起來最好的選項，最後卻不一定能得到整體最佳解。
我們也利用動態規劃，從較小金額的答案逐步推導，找出了真正的最少硬幣數。
這兩種方法的差別提醒了我們：

現在做出的選擇，會改變後面還有哪些可能

而現實世界裡，問題往往不只是在「選哪一個」，還要考量：

有限的資源，到底應該留給哪些東西？

行李只能帶 20 公斤

假設你準備出國旅行。

航空公司規定托運行李最多只能 20 kg，但你想帶的東西很多：

現在問題來了，你當然可以說：

但它們的總重量是：

3 + 4 + 5 + 8 + 10
= 30 kg

超過 20 公斤，所以你不能全部帶，你必須開始做選擇。

問題不只是「塞得進去」

假設我們最後選了：

• 筆電
• 相機
• 書

總重量：

3 + 4 + 5 = 12 kg

當然塞得進去，但這並不代表它是一個好的答案。
因為問題可能已經不再糾結小於20公斤了，你可能會去想：

在不超過 20 公斤的前提下，怎麼讓帶走的東西總價值最高？

這裡就出現了兩個前面已經慢慢接觸過的概念：

• 限制條件（constraint）
• 最佳化目標

限制條件：哪些答案是允許的？

首先是限制條件，這個問題最明顯的限制條件是：

總重量 <= 20 kg

例如：

筆電 + 相機
3 + 4 = 7 kg

合法。
但：

衣服 + 登山裝備 + 相機
8 + 10 + 4 = 22 kg

就不合法。
所以 Knapsack 問題並不是在所有組合中直接挑價值最大的。

是先要求：

答案必須符合容量限制

符合限制條件的答案，稱為可行解（feasible solution）。

最佳化目標：在可行答案中，我們想要什麼？

光是可行還不夠。
例如筆電只有 3 公斤，當然符合限制。
但它的總價值只有 10，如果改成：

筆電 + 相機 + 登山裝備

重量是：

3 + 4 + 10
= 17 kg

總價值則是：

10 + 9 + 12
= 31

同樣沒有超過 20 公斤，但顯然第二個答案更好。
所以我們的最佳化目標是：

最大化總價值

現在問題可以更完整地描述成：

• 限制條件：總重量不能超過 20 kg
• 最佳化目標：讓被選中物品的總價值最大

這就是很多最佳化問題常見的基本形狀：

在限制條件之下，讓某個目標盡可能好

這次麻煩的是「組合」

如果每個物品只看自己的話，好像不難。
我們甚至可能開始想一些直覺規則：

價值最高的先拿？

那就先拿：

登山裝備：價值 = 12

接著：

筆電：價值 = 10

再拿：

相機：價值 = 9

得到：

10 + 3 + 4 = 17 kg

價值：

12 + 10 + 9 = 31

看起來不錯，但它還不是這組資料的最佳答案。
如果改成：

筆電 + 相機 + 書 + 衣服

總重量剛好是：

3 + 4 + 5 + 8 = 20 kg

總價值則是：

10 + 9 + 6 + 8 = 33

也就是說，「價值最高的先拿」得到 31，另一個組合卻能得到 33。
我們當然也可以改成「最輕的先拿」，或按照「價值與重量的比例」來選。
這些規則都有某種道理，卻不能只憑直覺保證一定得到整體最佳解。

因為現在每拿一個物品，都會占用一部分有限容量。
而你現在做的選擇，會改變之後還能選什麼。
例如剩下 5 kg 和剩下 9 kg，後面可以組合出的答案完全不同，所以這次困難的地方不是某一個物品好不好，而是：

哪些物品放在一起，才是最好的組合？

這就是 Knapsack Problem

這類問題有一個非常經典的名字：

背包問題 Knapsack Problem

最典型的版本裡，每個物品都有：

• 重量（weight）
• 價值（value）

背包則有一個最大容量（capacity），我們要決定每一樣物品拿或不拿，最後必須滿足：

總重量 <= 背包容量

同時盡可能讓總價值最大。
因為每件物品只能選一次，這個版本也稱為 0/1 背包問題。

如果用比較抽象的方式表示：

物品 A
重量 = 3
價值 = 10

物品 B
重量 = 4
價值 = 9

物品 C
重量 = 5
價值 = 6

我們要找的不是：

哪一件最好？

而是：

哪一組最好？

為什麼不能全部試一次？

看到這裡，很自然會想到：

那我把所有組合都試一遍，不就知道答案了嗎？

可以。
假設只有三個物品：A、B、C。
每個物品都只有兩種選擇：拿或不拿。

那所有可能大概就是：

都不拿

A
B
C

A + B
A + C
B + C

A + B + C

總共：8 種。
其實不多，如果是 4 個物品呢？

16 種

5 個：

32 種

10 個：

1024 種

20 個：

1,048,576 種

因為每多一個物品，就又多一個 拿 / 不拿 的選擇。

所以 n 個物品可能產生的組合數量，大致會來到：

2^n

這就是為什麼窮舉法（Brute Force）雖然概念非常簡單：

列出所有組合
→ 排除超重的
→ 找出價值最高的

但資料一多，很快就會開始變得昂貴。

窮舉法並不是「笨方法」

這裡也值得特別澄清。
窮舉法也常被稱為「暴力解」，所以很容易讓人覺得：

這是不是一種很爛的演算法？

其實不是，窮舉法最大的優點反而是：

它非常直接

你把所有可能答案列出來，再找出其中最好的。
只要真的有完整檢查，就不會漏掉整體最佳解。
真正的問題只是：

可能性太多

所以演算法設計裡一個很常見的問題就是：

我們能不能不要真的把所有可能性都重新算一次？

這正是動態規劃能派上用場的地方。

從窮舉走向動態規劃

上一篇的找零錢問題，用 dp[x] 記錄湊出金額 x 最少需要幾枚硬幣。

背包問題也能沿用類似的想法，只是這次需要同時記錄：

目前考慮到第幾件物品 + 背包還能使用多少容量

我們可以把狀態寫成：

dp[i][w]

代表「只考慮前 i 件物品，背包容量為 w 時，可以取得的最高價值」。

每遇到一件物品，只需要比較兩種可能：

• 不選它：沿用先前的最佳結果
• 選它：加上它的價值，並扣掉占用的容量

動態規劃不是憑某一條直覺規則決定下一件要拿什麼，而是把重複出現的較小問題記錄下來，再從這些結果組成整體答案。

有限資源會讓選擇彼此影響

Knapsack 背後其實是一個非常生活化的問題：

資源有限

有限的可能不只是行李重量。
也可能是：

• 時間
• 預算
• 記憶體
• CPU
• 人力
• 儲存空間

例如你今天只有 8 小時，但待辦事項有：

• 修 bug：3 小時，價值 8
• 寫文件：2 小時，價值 5
• 做新功能：6 小時，價值 10
• 補測試：3 小時，價值 7

問題其實跟行李很像：

• 重量 → 所需時間
• 價值 → 完成後的效益
• 容量 → 一天可以使用的時間

你需要要決定的是：

有限的 8 小時，要分配給哪些事情？

所以 Knapsack 不只是某個教科書裡的背包。
它描述的是：

有限資源下的組合選擇

同一件事，也可能有不同的最佳化目標

而且就像前面談最短路徑時一樣，問題怎麼定義，也會直接改變答案。

如果你出國是為了工作，那：

• 筆電價值 = 10
• 相機價值 = 3

但如果這次旅行的目標是攝影：

• 筆電價值 = 4
• 相機價值 = 10

同一組物品、同樣 20 公斤的限制，最佳組合可能完全不同。
因為：

價值並不是物品天生就有的數字

它往往是我們根據問題定義出來的。
這也再次回到這個系列一直在強調的事情：

演算法開始之前，必須先知道自己到底在最佳化什麼

Knapsack 要我們開始考慮整體

Greedy 問的是：

現在最好的是誰？

但背包問題還必須多問一步：

選或不選這件物品，會讓後面剩下哪些組合？

因此，我們衡量的不再是單一物品，而是：

限制條件 + 最佳化目標 + 組合

限制之下，不同選擇彼此組合後，哪一個整體結果最好？

從「選什麼」走向「怎麼分」

到目前為止，Knapsack 處理的是：

有限容量 + 從許多物品中挑一部分帶走

沒有被選中的物品可以放棄，我們只需要讓帶走的組合盡可能符合目標。
但如果把情境從旅行換成搬家，規則就不一樣了。
這一次，所有物品都必須運走，沒有任何一件可以被捨棄；每個箱子的容量卻仍然有限。
這時，我們不能再問：

哪些東西不要帶？

而是必須改問：

• 每件物品應該放進哪一個箱子？
• 總共需要幾個箱子？

Knapsack 關心的是挑選：

有限容量裡，哪些東西值得被選進來？

但當所有東西都必須被運走時，問題就會轉向分配(allocation）：

不是要不要選，而是該怎麼分配

下一篇，我們就來看看當物品不能被捨棄、每個容器的容量又有限時，問題會變成什麼模樣：

如何把所有物品分配完，又盡可能減少使用的容器？